1. Field of the Invention
The present invention relates to methods for coding and decoding low-density parity-check (LDPC) codes and a method for forming an LDPC parity check matrix, more particularly, to methods for coding and decoding LDPC codes and a method for forming an LDPC parity check matrix using a parity check matrix, which has a degree distribution conforming to a power-law function.
2. Discussion of Related Art
An LDPC code introduced first by Gallager in 1962 is a linear block code in which most of elements of a parity check matrix are zero. Related contents are described in “R. G. Gallager, Low-Density Parity-Check code,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, January 1962. However, the code was forgotten for a long time because it was difficult to implement a decoder with technologies at that time, and then has been rediscovered by Mackay, et al. Related contents are described in “D. J. C. MacKay, Good error correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, March 1999. Iterative decoding using sum-product (summation and multiplication) algorithms allows such an LDPC code to hold excellent error recovery performance. In particular, it has been shown (ascertained) that if the LDPC code is configured to be not uniform, namely, an irregular LDPC code, it results in excellent performance over a turbo code. Related contents are described in “T. J. Richardson, M. A. Shokrollashi, and R. L. Urbanke, Design of capacity approaching irregular low-density parity-check codes,” IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 619-637, February 2001. The performance of the LDPC code is generally determined by a configuration of the parity check matrix.
The encoding of the LDPC code can be achieved by an equation of c=aG. In the equation, c means an encoded code vector, a is an information vector, and G corresponds to a parity generation matrix. The parity generation matrix G and the parity check matrix H satisfy an equation, cHT=aGHT=O, for all codewords c or all information vectors a. In the equation, O means a zero vector. In FIG. 1, denoted are examples of the information vector a, the parity generation matrix G, the code vector c, the parity check matrix H, and the zero vector O.
The decoding of the LDPC codes may use a bipartite graph depicted in FIG. 2. The bipartite graph in FIG. 2 corresponds to the parity check matrix shown in FIG. 1. The bipartite graph is composed of check nodes 110 and variable nodes 120, and the variable nodes 120 are composed of information nodes 122 and parity nodes 124. The number of the check nodes 110 is equal to the number of rows in the parity check matrix, and the number of the variable node 120 is equal to the number of columns in the parity check matrix, namely, a length of the code vector. Lines that connect between the check node 110 and the variable node 120 are called edges 130. The edges insertions follow the positions of 1 s of the parity matrix. For example, since there are 1 s at the first, fourth, sixth and seventh columns of the first row in the parity check matrix H of FIG. 1, the first check node of FIG. 2 is connected to the first, fourth, sixth and seventh variable nodes by the edges. Decoding of the LDPC codes is done by an iterative belief propagation via the edge nodes between the check nodes 110 and the variable nodes 120. Related contents are described in “D. J. C MacKay, Good error correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45. pp. 399-431, March 1999.
Design of a good connection structure of a bipartite graph, on which the LDPC code is based, is of prime importance in constructing the LDPC codes. This is because the connection structure between nodes in the graph directly determines the performance of the LDPC code. An LDPC code may be represented by a bipartite graph consisting of variable nodes and check nodes, as described above. The number of edges connected to the node is called the degree of the node. It is known that the performance of codes formulated on the graph is determined by the degree distribution of the graph on the assumption that the graph is a random graph having a tree structure and does not have a cycle therein. Given the degree distribution of the graph, the performance of the graph can be calculated by the density evolution method developed by Richardson, et al. Related contents are described in “T. J. Richardson, R. L. Urbanke, IEEE Trans. Inform. Theory 47, 599, 2001” and “T. J. Richardson, M. A. Shokrollahi, R. L. Urbanke, IEEE Trans. Inform. Theory 47, 619, 2001.”
A conventional method for designing the connection structure of the graph, namely, constructing a parity check matrix used for the LDPC codes includes the degree optimization though numerical calculation. On the other hand, codes that provide mathematic expressions for the degree distribution include Tornado code developed by Luby, et al., a right-regular sequence of Shokrollahi, and the like. However, such formation of the LDPC codes according to the prior art requires massive numerical computation and finding an optimal solution is not a feasible task, as is similar to a typical global optimization problem.